{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge Two Sorted Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeTwoLists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并两个有序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>将两个升序链表合并为一个新的 <strong>升序</strong> 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 </p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg\" style=\"width: 662px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [1,2,4], l2 = [1,3,4]\n",
    "<strong>输出：</strong>[1,1,2,3,4,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [], l2 = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [], l2 = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两个链表的节点数目范围是 <code>[0, 50]</code></li>\n",
    "\t<li><code>-100 <= Node.val <= 100</code></li>\n",
    "\t<li><code>l1</code> 和 <code>l2</code> 均按 <strong>非递减顺序</strong> 排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-two-sorted-lists](https://leetcode.cn/problems/merge-two-sorted-lists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-two-sorted-lists](https://leetcode.cn/problems/merge-two-sorted-lists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4]\\n[1,3,4]', '[]\\n[]', '[]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return\n",
    "        if len(lists)==1:\n",
    "            return lists[0]\n",
    "\n",
    "        def mergeTwoLists(l1, l2):\n",
    "            if not l1 and not l2:\n",
    "                return \n",
    "            if not l1:\n",
    "                return l2\n",
    "            if not l2:\n",
    "                return l1\n",
    "            cur1=l1\n",
    "            cur2=l2\n",
    "            helpcur=ListNode(1)\n",
    "            start=helpcur\n",
    "            while cur1 and cur2:\n",
    "                if cur1.val<=cur2.val:\n",
    "                    helpcur.next=cur1\n",
    "                    cur1=cur1.next\n",
    "                else:\n",
    "                    helpcur.next=cur2\n",
    "                    cur2=cur2.next\n",
    "                helpcur=helpcur.next\n",
    "            if cur1:\n",
    "                helpcur.next=cur1\n",
    "            elif cur2:\n",
    "                helpcur.next=cur2\n",
    "            return start.next\n",
    "        i=1\n",
    "        cur=lists[i-1]\n",
    "        while i<len(lists):\n",
    "            cur=mergeTwoLists(cur,lists[i])\n",
    "            i+=1\n",
    "        return cur\n",
    "       \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if l1 is None or l1.val is None:\n",
    "            return l2\n",
    "        if l2 is None or l2.val is None:\n",
    "            return l1\n",
    "        \n",
    "        curr_l1 = l1\n",
    "        curr_l2 = l2\n",
    "        result = ListNode(l1.val)\n",
    "        curr_result = result\n",
    "        while True:\n",
    "            if curr_l1 is None or curr_l1.val is None:\n",
    "                curr_result.next = curr_l2\n",
    "                break\n",
    "            if curr_l2 is None or curr_l2.val is None:\n",
    "                curr_result.next = curr_l1\n",
    "                break\n",
    "                \n",
    "            if curr_l1.val < curr_l2.val:\n",
    "                curr_result.next = ListNode(curr_l1.val)\n",
    "                curr_l1 = curr_l1.next\n",
    "            else:\n",
    "                curr_result.next = ListNode(curr_l2.val)\n",
    "                curr_l2 = curr_l2.next\n",
    "            curr_result = curr_result.next\n",
    "        \n",
    "        return result.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=21 lang=python3\r\n",
    "#\r\n",
    "# [21] 合并两个有序链表\r\n",
    "#\r\n",
    "# https://leetcode-cn.com/problems/merge-two-sorted-lists/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Easy (51.86%)\r\n",
    "# Total Accepted:    40.3K\r\n",
    "# Total Submissions: 77.8K\r\n",
    "# Testcase Example:  '[1,2,4]\\n[1,3,4]'\r\n",
    "#\r\n",
    "# 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 \r\n",
    "# \r\n",
    "# 示例：\r\n",
    "# \r\n",
    "# 输入：1->2->4, 1->3->4\r\n",
    "# 输出：1->1->2->3->4->4\r\n",
    "# \r\n",
    "# \r\n",
    "#\r\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.next = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def mergeTwoLists(self, l1, l2):\r\n",
    "        \"\"\"\r\n",
    "        :type l1: ListNode\r\n",
    "        :type l2: ListNode\r\n",
    "        :rtype: ListNode\r\n",
    "        \"\"\"\r\n",
    "        if not l1:\r\n",
    "            return l2\r\n",
    "        elif not l2:\r\n",
    "            return l1\r\n",
    "\r\n",
    "        if l1.val<l2.val:\r\n",
    "            head = l1\r\n",
    "            l1 = l1.next\r\n",
    "        else:\r\n",
    "            head = l2\r\n",
    "            l2 = l2.next\r\n",
    "        node = head\r\n",
    "\r\n",
    "        while l1 and l2:\r\n",
    "            if l1.val < l2.val:\r\n",
    "                node.next = l1\r\n",
    "                l1 = l1.next\r\n",
    "            else:\r\n",
    "                node.next = l2\r\n",
    "                l2 = l2.next\r\n",
    "            node = node.next\r\n",
    "        if l1 == None:\r\n",
    "            node.next = l2\r\n",
    "        else:\r\n",
    "            node.next = l1\r\n",
    "        return head\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        a,b = l1,l2\n",
    "        dummy = cur = ListNode(0)\n",
    "        \n",
    "        while a and b:\n",
    "            if a.val < b.val:\n",
    "                cur.next = ListNode(a.val)\n",
    "                a = a.next\n",
    "            else:\n",
    "                cur.next = ListNode(b.val)\n",
    "                b = b.next\n",
    "            cur = cur.next\n",
    "        if a:\n",
    "            cur.next = a\n",
    "        if b:\n",
    "            cur.next = b\n",
    "        return dummy.next\n",
    "                \n",
    "#         if not l1:\n",
    "#             return l2\n",
    "#         # If l2 is empty, return l1\n",
    "#         if not l2:\n",
    "#             return l1\n",
    "#         #If l1 val is lesser than l2, make temp point to l1 and move l1 to next element.\n",
    "#         #Get next element by recursively calling the function\n",
    "#         if l1.val <= l2.val:\n",
    "#             temp = l1\n",
    "#             temp.next = self.mergeTwoLists(l1.next, l2)\n",
    "\n",
    "#         #If l2 val is lesser than l2, make temp point to l2 and move l2 to next element.\n",
    "#         #Get next element by recursively calling the function\n",
    "#         else:\n",
    "#             temp = l2\n",
    "#             temp.next = self.mergeTwoLists(l1, l2.next)\n",
    "#         return temp\n",
    "#         if l1 is None:\n",
    "#             return l2\n",
    "#         if l2 is None:\n",
    "#             return l1\n",
    "\n",
    "#         if (l1.val < l2.val):\n",
    "#             l1.next = self.mergeTwoLists(l1.next, l2)\n",
    "#             return l1\n",
    "#         else:\n",
    "#             l2.next = self.mergeTwoLists(l2.next, l1)\n",
    "#             return l2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=21 lang=python3\n",
    "#\n",
    "# [21] 合并两个有序链表\n",
    "#\n",
    "# https://leetcode-cn.com/problems/merge-two-sorted-lists/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (52.01%)\n",
    "# Total Accepted:    41.8K\n",
    "# Total Submissions: 80.2K\n",
    "# Testcase Example:  '[1,2,4]\\n[1,3,4]'\n",
    "#\n",
    "# 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。\n",
    "#\n",
    "# 示例：\n",
    "#\n",
    "# 输入：1->2->4, 1->3->4\n",
    "# 输出：1->1->2->3->4->4\n",
    "#\n",
    "#\n",
    "#\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if l1 is None and l2 is None:\n",
    "            return None\n",
    "        if l1 is None and l2 is not None:\n",
    "            return l2\n",
    "        if l1 is not None and l2 is None:\n",
    "            return l1\n",
    "        left = right = 0\n",
    "        result = []\n",
    "        l1_len = self.get_len(l1)\n",
    "        l2_len = self.get_len(l2)\n",
    "\n",
    "        print('l1_len', l1_len)\n",
    "        print('l2_len', l2_len)\n",
    "        while left <= l1_len and right <= l2_len:\n",
    "            if l1.val <= l2.val:\n",
    "                result.append(l1.val)\n",
    "                l1 = l1.next\n",
    "                left += 1\n",
    "            else:\n",
    "                result.append(l2.val)\n",
    "                l2 = l2.next\n",
    "                right += 1\n",
    "        while left <= l1_len:\n",
    "            result.append(l1.val)\n",
    "            l1 = l1.next\n",
    "            left += 1\n",
    "        while right <= l2_len:\n",
    "            result.append(l2.val)\n",
    "            l2 = l2.next\n",
    "            right += 1\n",
    "        return result\n",
    "\n",
    "    def get_len(self, l):\n",
    "        length = 0\n",
    "        while l.next != None:\n",
    "            length += 1\n",
    "            l = l.next\n",
    "        return length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if l1 is None:return l2\n",
    "        if l2 is None:return l1\n",
    "        \n",
    "        head=None\n",
    "        \n",
    "        if l1.val<l2.val:\n",
    "            head=l1\n",
    "            l1=l1.next\n",
    "        else:\n",
    "            head=l2\n",
    "            l2=l2.next\n",
    "            \n",
    "        temp=head\n",
    "        \n",
    "        while l1 and l2:\n",
    "            if l1.val<l2.val:\n",
    "                temp.next=l1\n",
    "                temp=temp.next\n",
    "                l1=l1.next\n",
    "            else:\n",
    "                temp.next=l2\n",
    "                temp=temp.next\n",
    "                l2=l2.next\n",
    "                \n",
    "        if l1 is None:\n",
    "            temp.next=l2\n",
    "        \n",
    "        if l2 is None:\n",
    "            temp.next=l1\n",
    "            \n",
    "        return head\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l=ListNode(0)\n",
    "        r=l\n",
    "        while l1!=None and l2!=None:\n",
    "            if l1.val<=l2.val:\n",
    "                l.next=l1\n",
    "                l=l.next\n",
    "                l1=l1.next\n",
    "            else:\n",
    "                l.next=l2\n",
    "                l=l.next\n",
    "                l2=l2.next\n",
    "        if l1!=None:\n",
    "            l.next=l1\n",
    "        if l2!=None:\n",
    "            l.next=l2\n",
    "        return r.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        head = merge = ListNode(0)\n",
    "        \n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                merge.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                merge.next = l2\n",
    "                l2 = l2.next\n",
    "            print(merge.val)\n",
    "            merge = merge.next\n",
    "        if l1:\n",
    "            merge.next = l1\n",
    "        if l2:\n",
    "            merge.next = l2\n",
    "        \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        elif l2 is None:\n",
    "            return l1\n",
    "        elif l1 is None and l2 is None:\n",
    "            return None\n",
    "        \n",
    "        TheNode = ListNode(0)\n",
    "        FirstNode = TheNode\n",
    "        while True:\n",
    "            print(l1.val, l2.val)\n",
    "            if l1.val < l2.val:\n",
    "                TheNode.val = l1.val\n",
    "                if l1.next is None:\n",
    "                    TheNode.next = l2\n",
    "                    break\n",
    "                l1 = l1.next\n",
    "                TheNode.next = ListNode(0)\n",
    "                TheNode = TheNode.next\n",
    "            else:\n",
    "                TheNode.val = l2.val\n",
    "                if l2.next is None:\n",
    "                    TheNode.next = l1\n",
    "                    break\n",
    "                l2 = l2.next\n",
    "                TheNode.next = ListNode(0)\n",
    "                TheNode = TheNode.next\n",
    "        return FirstNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        tempNode=ListNode(0)\n",
    "        newNode=tempNode\n",
    "        while l1 or l2:\n",
    "            if not l1:\n",
    "                newNode.next=l2\n",
    "                l2=l2.next\n",
    "            elif not l2:\n",
    "                newNode.next=l1\n",
    "                l1=l1.next\n",
    "            else:\n",
    "                print(l1.val,l2.val)\n",
    "                if l1.val<=l2.val:\n",
    "                    newNode.next=l1\n",
    "                    l1=l1.next\n",
    "                else:\n",
    "                    newNode.next=l2\n",
    "                    l2=l2.next\n",
    "           \n",
    "            newNode=newNode.next\n",
    "        return tempNode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        elif l2 is None:\n",
    "            return l1\n",
    "        elif l1.val<l2.val:\n",
    "            l1.next=self.mergeTwoLists(l1.next,l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next=self.mergeTwoLists(l2.next,l1)\n",
    "            return l2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        if l2 is None:\n",
    "            return l1 \n",
    "        if l1.val<=l2.val:\n",
    "            l1.next=self.mergeTwoLists(l1.next,l2)\n",
    "            return l1\n",
    "        else :\n",
    "            l2.next=self.mergeTwoLists(l2.next,l1)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        new_list = list()\n",
    "        if l1 is not None:\n",
    "            new_list += self.node_to_list(l1)\n",
    "        if l2 is not None:\n",
    "            new_list += self.node_to_list(l2)\n",
    "        new_list.sort()\n",
    "        new_list.reverse()\n",
    "        if new_list == list():\n",
    "            return None\n",
    "        else:\n",
    "            new_node = self.list_to_node(new_list)\n",
    "            return new_node\n",
    "        \n",
    "    def node_to_list(self, l: ListNode) -> list:\n",
    "        new_list = list()\n",
    "        tmp = l\n",
    "        while tmp.next is not None:\n",
    "            new_list.append(tmp.val)\n",
    "            tmp = tmp.next\n",
    "        new_list.append(tmp.val)\n",
    "        return new_list\n",
    "    \n",
    "    def list_to_node(self, new_list: list) -> ListNode:\n",
    "        head_node = ListNode(new_list[0])\n",
    "        for each in new_list[1:]:\n",
    "            tmp_node = ListNode(each)\n",
    "            tmp_node.next = head_node\n",
    "            head_node = tmp_node\n",
    "        return head_node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        res=ListNode(-1)\n",
    "        pre=res\n",
    "        res.val=None\n",
    "        while l1!=None and l2!=None:\n",
    "            if l1.val<=l2.val:\n",
    "                pre.next=l1\n",
    "                pre=l1\n",
    "                l1=l1.next\n",
    "            elif l2.val<=l1.val:\n",
    "                pre.next=l2\n",
    "                pre=l2\n",
    "                l2=l2.next\n",
    "        if l2==None:\n",
    "            pre.next=l1\n",
    "        elif l1==None:\n",
    "            pre.next=l2\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        prehead = ListNode(-1)\n",
    "        prev = prehead\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                prev.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                prev.next = l2\n",
    "                l2 = l2.next\n",
    "            prev = prev.next\n",
    "        prev.next = l1 if l1 else l2\n",
    "        #print(prev)\n",
    "        return prehead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        \n",
    "        # dummy = ListNode(0)\n",
    "        # # 有个游标，标识 结果链表 的结尾\n",
    "        # move = dummy\n",
    "        # # l1 和 l2 都未遍历结束\n",
    "        # while l1 or l2:\n",
    "        #     # 如果 l1 的数值比较小\n",
    "        #     if l1.val <= l2.val:\n",
    "        #         # 把 l1 头部节点拼接到 结果链表 的结尾\n",
    "        #         move.next = l1\n",
    "        #         # l1 指向下一个节点\n",
    "        #         l1 = l1.next\n",
    "        #     else:\n",
    "        #         # 把 l2 头部节点拼接到 结果链表 的结尾\n",
    "        #         move.next = l2\n",
    "        #         # l2 指向下一个节点\n",
    "        #         l2 = l2.next\n",
    "        #     # 移动 结果链表 的结尾指针\n",
    "        #     move = move.next\n",
    "        # # l1 或者 l2 尚未使用完，拼接到 结果链表 的最后\n",
    "        # move.next = l1 if l1 else l2\n",
    "        # # 返回哑节点的下一个位置\n",
    "        # return dummy.next\n",
    "\n",
    "\n",
    "        l3=ListNode(0)\n",
    "        \n",
    "        move=l3\n",
    "        while l1 and l2:\n",
    "            # if not l1:\n",
    "            #     return l2\n",
    "            # if not l2:\n",
    "            #     return l1\n",
    "\n",
    "            if l1.val <= l2.val:\n",
    "                move.next=l1\n",
    "                \n",
    "                l1=l1.next\n",
    "            else:\n",
    "                move.next=l2\n",
    "                l2=l2.next\n",
    "                \n",
    "                \n",
    "            move = move.next\n",
    "        move.next = l1 if l1 else l2\n",
    "        return l3.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 and l2:\n",
    "            if l1.val > l2.val: l1, l2 = l2, l1\n",
    "            l1.next = self.mergeTwoLists(l1.next, l2)\n",
    "        return l1 or l2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        infinity = 2**32\n",
    "        l3 = ListNode(-1)\n",
    "        p1 = l1\n",
    "        p2 = l2\n",
    "        p3 = l3\n",
    "        while p1 is not None or p2 is not None:\n",
    "            v1 = infinity if p1 is None else p1.val\n",
    "            v2 = infinity if p2 is None else p2.val\n",
    "            if v1 < v2:\n",
    "                p1 = p1.next\n",
    "                p3.next = ListNode(v1)\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "                p3.next = ListNode(v2)\n",
    "            p3 = p3.next\n",
    "        return l3.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        elif not l2:\n",
    "            return l1\n",
    "        elif l1.val <= l2.val:\n",
    "            l1.next = self.mergeTwoLists(l1.next,l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.mergeTwoLists(l1,l2.next)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1: return l2  # 终止条件，直到两个链表都空\n",
    "        if not l2: return l1\n",
    "        if l1.val <= l2.val:  # 递归调用\n",
    "            print(\"l1.val<=l2.val: \", l1)\n",
    "            l1.next = self.mergeTwoLists(l1.next,l2)\n",
    "            print(\"l1.val<=l2.val: \", l1)\n",
    "            return l1\n",
    "        else:\n",
    "            print(\"l1.val>l2.val: \", l2)   \n",
    "            l2.next = self.mergeTwoLists(l1,l2.next)\n",
    "            print(\"l1.val>l2.val: \", l2)            \n",
    "            return l2\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "       temp = ListNode(0)\n",
    "       l3 = temp\n",
    "       while(l1!=None and l2!=None):\n",
    "            print(l1.val,l2.val)\n",
    "            if(l1.val<l2.val):\n",
    "                new =  ListNode(l1.val)\n",
    "                l3.next = new\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                new = ListNode(l2.val)\n",
    "                l3.next = new\n",
    "                l2 = l2.next\n",
    "            l3 = l3.next\n",
    "       #print(temp.next)\n",
    "       l3.next = l1 if l1!=None else l2\n",
    "       return temp.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def printnode(head):\n",
    "            print(\"打印链表\")\n",
    "            pnode=ListNode(None)\n",
    "            \n",
    "            pnode=head\n",
    "\n",
    "##            pnode=head.next\n",
    "            while (pnode !=None ):\n",
    "                 print(pnode.val,end=' ')\n",
    "                 pnode=pnode.next\n",
    "                 print()\n",
    "            return\n",
    "        \n",
    "##        print(\"l1:  \",end='')\n",
    "##        printnode(l1)\n",
    "##        print(\"l2:  \",end='')\n",
    "##        printnode(l2)\n",
    "        \n",
    "        p1=ListNode(None)\n",
    "        link1=ListNode(None)\n",
    "        link2=ListNode(None)\n",
    "##        mcur=M\n",
    "\n",
    "##        if l1==None and l2 ==None:\n",
    "##           return None\n",
    "##        if l1.next!=None:\n",
    "##           link1=l1.next\n",
    "##        if l2.next!=None:\n",
    "##           link2=l2.next\n",
    "\n",
    "        if l1!=None and l1.val==None and l1.next!=None:\n",
    "            print(\"l1!=None and l1.val==None and l1.next!=None:\")\n",
    "            l1=l1.next\n",
    "        if l2!=None and l2.val==None and l2.next!=None:\n",
    "           print(\"l1!=None and l1.val==None and l1.next!=None:\")\n",
    "           l2=l2.next       \n",
    "            \n",
    "##\n",
    "\n",
    "        M1=ListNode(None)\n",
    "        mcur=ListNode(None)\n",
    "        #mcur=l1\n",
    "        M1=mcur\n",
    "        print(\"link2.val\",link2.val)\n",
    "        \n",
    "        if l1==None and l2 ==None:\n",
    "            return\n",
    "        elif  l1!=None and l2==None:\n",
    "            print(\" link1!=None and link2==None: \")\n",
    "            return l1\n",
    "        elif l1==None and l2!=None:\n",
    "            print(\" link1==None and link2!=None: \")            \n",
    "            return l2\n",
    "\n",
    "        \n",
    "        def meger (cur,link1,link2 ):\n",
    "            M1=ListNode(None)\n",
    "            mcur=ListNode(None)\n",
    "            mcur=cur\n",
    "\n",
    "            print(\"link1:  \",end='')\n",
    "            printnode(link1)\n",
    "            print(\"link2:  \",end='')\n",
    "            printnode(link2)\n",
    "        \n",
    "\n",
    "            #print(\"merge\",link1,link2)\n",
    "            \n",
    "\n",
    "            if link1!=None and link1.val==None:\n",
    "                link1=link1.next\n",
    "            if link2!=None and link2.val==None:\n",
    "                link2=link2.next\n",
    "            \n",
    "            \n",
    "            if link1 !=None and link2==None:\n",
    "                mcur.next=link1\n",
    "                print(\"link1 !=None and link2==None mcur\",mcur.val)\n",
    "                #return mcur\n",
    "                       \n",
    "            elif link1 ==None  and link2!=None:\n",
    "                mcur.next=link2\n",
    "                print(\"link1 ==None and link2!=None: mcur\",mcur.val)\n",
    "                #return mcur\n",
    "               \n",
    "            else:\n",
    "                if link1.val<=link2.val:\n",
    "                    mcur.next=link1\n",
    "                    print(\"link1.val \",link1.val)\n",
    "                    if link1.next !=None:\n",
    "                        link1=link1.next\n",
    "                    else:\n",
    "                        link1=None\n",
    "                    mcur=mcur.next               \n",
    "                    mcur=meger(mcur,link1,link2)\n",
    "                elif link1.val>link2.val:\n",
    "                    print(\"link2.val \",link2.val)\n",
    "                    mcur.next=link2\n",
    "                    if link2.next !=None:\n",
    "                        link2=link2.next\n",
    "                    else:\n",
    "                        link2=None\n",
    "                    mcur=mcur.next\n",
    "                    mcur=meger(mcur,link1,link2)\n",
    "            return mcur\n",
    "\n",
    "        meger(mcur,l1,l2)\n",
    "##        print(\" M1.next.val \",M1.val,M1.next.val,M1.next.next.val)\n",
    "        printnode(M1)\n",
    "##        \n",
    "        return  M1.next\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        p = ListNode()\n",
    "        c = p\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                p.next = ListNode(l1.val)\n",
    "                p = p.next\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                p.next = ListNode(l2.val)\n",
    "                p = p.next\n",
    "                l2 = l2.next\n",
    "        if l1:\n",
    "            p.next = l1\n",
    "        else:\n",
    "            p.next = l2\n",
    "        return c.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        a = ListNode(-1)\n",
    "        c = a\n",
    "        while list1 and list2:\n",
    "            if list1.val <= list2.val:\n",
    "                c.next = list1\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                c.next = list2\n",
    "                list2 = list2.next\n",
    "            c = c.next\n",
    "        c.next = list1 if list1 is not None else list2\n",
    "        return a.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        '''\n",
    "        # 利用递归，每次指向下一个\n",
    "        if not list1: return list2\n",
    "        if not list2: return list1\n",
    "        if list1.val <= list2.val:\n",
    "            list1.next = self.mergeTwoLists(list1.next, list2)\n",
    "            return list1\n",
    "        else:\n",
    "            list2.next = self.mergeTwoLists(list1, list2.next)\n",
    "            return list2\n",
    "        '''\n",
    "        dummy = ListNode(-1)\n",
    "        prev = dummy\n",
    "        while list1 and list2:\n",
    "            if list1.val <= list2.val:\n",
    "                prev.next = list1\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                prev.next = list2\n",
    "                list2 = list2.next\n",
    "            prev = prev.next\n",
    "        prev.next = list1 if list1 else list2\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p, q = list1, list2\n",
    "        res = ListNode()\n",
    "        r = res\n",
    "        while p is not None and q is not None:\n",
    "            if p.val < q.val:\n",
    "                r.next = p\n",
    "                r = r.next\n",
    "                p = p.next\n",
    "            else:\n",
    "                r.next = q\n",
    "                r = r.next\n",
    "                q = q.next\n",
    "        while p is not None:\n",
    "            r.next = p\n",
    "            r = r.next\n",
    "            p = p.next\n",
    "        \n",
    "        while q is not None:\n",
    "            r.next = q\n",
    "            r = r.next\n",
    "            q = q.next\n",
    "        return res.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1: return l2  # 终止条件，直到两个链表都空\n",
    "        if not l2: return l1\n",
    "        if l1.val <= l2.val:  # 递归调用\n",
    "            l1.next = self.mergeTwoLists(l1.next,l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.mergeTwoLists(l1,l2.next)\n",
    "            return l2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        if list1 ==None:\n",
    "            return list2\n",
    "        if list2 == None:\n",
    "            return list1\n",
    "\n",
    "        l1 = ListNode(0,list1)\n",
    "        l2 = ListNode(0,list2)\n",
    "        l3 = ListNode()\n",
    "        cur1,cur2,cur3 = list1,list2,l3\n",
    "\n",
    "        while cur1 != None and cur2 != None:\n",
    "            if cur1.val <= cur2.val:\n",
    "                cur3.next = cur1  #cur3移动到cur1 \n",
    "                l1.next = cur1.next    #第一个链表删除第一个节点，自己指向自己\n",
    "                cur1 = l1.next          \n",
    "                cur3 = cur3.next      #合并的链表循环到尾部\n",
    "                cur3.next = None      #设置结束\n",
    "                print(l3)\n",
    "            else:\n",
    "                cur3.next = cur2  #cur3移动到cur1 \n",
    "                l2.next = cur2.next    #第一个链表删除第一个节点，自己指向自己\n",
    "                cur2 = l2.next          \n",
    "                cur3 = cur3.next      #合并的链表循环到尾部\n",
    "                cur3.next = None      #设置结束\n",
    "                print(l3)\n",
    "        if cur1 == None:\n",
    "            cur3.next = cur2\n",
    "        if cur2 == None:\n",
    "            cur3.next = cur1\n",
    "        return l3.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l = list1\n",
    "        r = list2\n",
    "        if not l and not r:\n",
    "            return l\n",
    "        elif not l:\n",
    "            return r\n",
    "        elif not r:\n",
    "            return l\n",
    "        tempq = ListNode\n",
    "        temp = tempq\n",
    "        while l and r:\n",
    "            if l.val <= r.val:\n",
    "                temp.next = l\n",
    "                temp = l\n",
    "                l = l.next\n",
    "\n",
    "            else:\n",
    "                temp.next = r\n",
    "                temp = r\n",
    "                r = r.next\n",
    "        if not r:\n",
    "            temp.next = l\n",
    "        else:\n",
    "            temp.next = r\n",
    "        return tempq.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        node = ListNode()\n",
    "        fir = node\n",
    "        if not list1:\n",
    "            return list2\n",
    "        if not list2:\n",
    "            return list1\n",
    "        if not list1 and list2:\n",
    "            return []\n",
    "\n",
    "        while list1 and list2:\n",
    "            if list1.val < list2.val:\n",
    "                fir.next = ListNode(list1.val)\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                fir.next = ListNode(list2.val)\n",
    "                list2 = list2.next\n",
    "            fir = fir.next\n",
    "        if list1:\n",
    "            fir.next = list1\n",
    "        if list2:\n",
    "            fir.next = list2\n",
    "        return node.next\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()  # 新链表的头节点，是哑节点\n",
    "        cur = dummy  # 新链表的当前节点\n",
    "\n",
    "        # 遍历list1和list2，哪个小就把哪个加入新链表\n",
    "        while list1 is not None and list2 is not None:\n",
    "            if list1.val < list2.val:\n",
    "                cur.next = list1\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                cur.next = list2\n",
    "                list2 = list2.next\n",
    "            cur = cur.next\n",
    "\n",
    "        # list1和list2可能不等长，拼接剩下的链表\n",
    "        cur.next = list1 if list1 is not None else list2\n",
    "\n",
    "        return dummy.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
